package HighMethod09;

import java.util.Arrays;

/**
 * 旅行者售货员问题
 * 带权路径图
 */

class Graph {
    int n;      //顶点个数
    int c;      //当前路径下的最小费用
    int cc;     //最终最优路径，既费用最小
    int[] x;    //当前路径
    int[] cx;      //最优路径
    int[][] cost;

    public Graph(int v) {
        n = v;
        c = cc = 0;         //初始化
        x = new int[n + 1];         //不使用0下标
        cx = new int[n + 1];
        cost = new int[n + 1][n + 1];

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                cost[i][j] = Integer.MAX_VALUE;
            }
        }
        for (int i = 1; i <= n; i++) {
            cost[i][i] = 0;
        }
        //本来应该是读取文件,初始化路经长度既权值
        cost[1][2] = cost[2][1] = 30;
        cost[1][3] = cost[3][1] = 6;
        cost[1][4] = cost[4][1] = 4;
        cost[2][3] = cost[3][2] = 5;
        cost[2][4] = cost[4][2] = 10;
        cost[3][4] = cost[4][3] = 20;
    }

    /**
     * @param v 顶点参数
     * @return
     */
    public int MinPath(int v) {
        if (v < 0 || v > n) {
            return -1;
        }

        for (int i = 1; i <= n; i++) {
            x[i] = i;
        }
        Swap_Ar(x, 1, v);
        cc = Integer.MAX_VALUE;

        BackTack(2);        //当前起始点并不参与当前排列
//        System.out.println(Arrays.toString(cx));
//        System.out.println(Arrays.toString(x));
        return cc;
    }

    private void BackTack(int i) {
        if (i == n) {
            if (cost[x[i - 1]][x[i]] != Integer.MAX_VALUE && cost[x[i]][1] != Integer.MAX_VALUE &&
                    (c + cost[x[i - 1]][x[i]] + cost[x[i]][1]) < cc) {

                cc = c + cost[x[i - 1]][x[i]] + cost[x[i]][1];
                for (int j = 1; j <= n; ++j) {      //更新最优路径
                    cx[j] = x[j];
                }
            }

        } else {
            for (int j = i; j <= n; j++) {       //存在连接边,并且当前最优花费小于全局最优
                if (cost[x[i - 1]][x[j]] != Integer.MAX_VALUE && c + cost[x[i - 1]][x[j]] < cc) {
                    Swap_Ar(x, j, i);
                    c += cost[x[i - 1]][x[i]];
                    BackTack(i + 1);
                    c -= cost[x[i - 1]][x[i]];
                    Swap_Ar(x, i, j);

                }
            }
        }
    }

    private void Swap_Ar(int[] ar, int i, int j) {
        int tmp = ar[i];
        ar[i] = ar[j];
        ar[j] = tmp;
    }
}


public class Traveler {

    public static void main(String[] args) {
        Graph myg = new Graph(4);
        int minpath = myg.MinPath(1);
        System.out.println(minpath);

    }
}
